import java.util.*;

/**
 * @author LKQ
 * @date 2022/2/25 23:07
 * @description 拓扑排序 + 动态规划 数据量小可通过，但无法Ac
 */
public class Solution {
    public static void main(String[] args) {
        int[][] relations = {{2,7}, {2,6}, {3,6},{4,6}, {7,6}, {2,1}, {3,1}, {4,1}, {6,1},{7,1},{3,8},{5,8},{7,8},{1,9},{2,9},{6,9},{7,9}};
        int[] time = {9,5,9,5,8,7,7,8,4};
    }
    public int minimumTime(int n, int[][] relations, int[] time) {
        // 每门课完成的时间
        int[] dp = new int[n+1];
        // 统计每门课的前导课
        Map<Integer, List<Integer>> map = new HashMap<>();
        for(int[] re: relations) {
            List<Integer> temp = new ArrayList<>();
            if (map.containsKey(re[1])) {
                temp = map.get(re[1]);
            }
            temp.add(re[0]);
            map.put(re[1], temp);
        }
        // 存在前课的课程所需时间
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 1; i <= n; i++) {
            if (!map.containsKey(i)) {
                dp[i] = time[i - 1];
            }else {
                queue.add(i);
            }
        }
        // 处理拥有前导课程的
        while (!queue.isEmpty()) {
            int i = queue.poll();
            List<Integer> list = map.get(i);
            int max = 0;
            boolean finish = true;
            // 如果当前节点的前导课程中存在没有结束的课程，那么将这个课程放到队列末端，然后继续访问下一个
            for(int j : list) {
                if(dp[j] == 0) {
                    queue.offer(i);
                    finish = false;
                    break;
                }
                max = Math.max(max, dp[j]);
            }
            if (!finish) {
                continue;
            }
            dp[i] = max + time[i - 1];
        }
        int ans = 0;
        for (int i = 0; i < n + 1; i++) {
            ans= Math.max(dp[i] , ans);
        }
        return ans;
    }
}
